package com.it.od.od2024.od20240306;

/**
 * @author: liminghui
 * @date: 2024/3/5 22:38
 * @version: 1.0
 * @description: 最多购买多少珠宝
 * 橱窗里有一排宝石，不同的宝石对应不同的价格，宝石的价格标记为gems[i],0<=i<n, n = gems.length
 * 宝石可同时出售0个或多个，如果同时出售多个，则要求出售的宝石编号连续；例如客户最大购买宝石个数为m，购买的宝石编号必须为gems[i],gems[i+1]...gems[i+m-1](0<=i<n,m<=n)
 * 假设你当前拥有总面值为value的钱，请问最多能购买到多少个宝石,如无法购买宝石，则返回0.
 * 用例1:
 * 7
 * 8
 * 4
 * 6
 * 3
 * 1
 * 6
 * 7
 * 10
 * 用例4:
 * 9
 * 1
 * 1
 * 1
 * 1
 * 1
 * 1
 * 1
 * 1
 * 1
 * 10
 */
public class Main1 {
    public static void main(String[] args) {
        // Scanner sc = new Scanner(new BufferedInputStream(System.in));
        // int n = sc.nextInt();
        // int[] gems = new int[n];
        // for (int i = 0; i < n; i++) {
        //     gems[i] = sc.nextInt();
        // }
        // int value = sc.nextInt();
        // int[] arr = {7, 8, 4, 6, 3, 1, 6, 7};
        // int c = 10;
        // int[] arr = {};
        // int c = 10;
        int[] arr = {9, 6, 1, 3, 1, 8, 9, 3, 2, 4};
        int c = 15;
        // int[] arr = {1, 1, 1, 1, 1, 1, 1, 1, 1};
        // int c = 10;
        int maxCount1 = method1(arr, c);
        System.out.println(maxCount1);
    }

    /**
     * 适合连续，双指针
     * @param gems
     * @param value
     * @return
     */
    private static int method1(int[] gems, int value) {
        int max = 0;
        for (int i = 0; i < gems.length; i++) {
            int sum = 0;
            for (int j = i; j < gems.length; j++) {
                sum += gems[i];
                if (sum > value) {
                    max = Math.max(max, j - i);
                    break;
                }
                if (j == gems.length - 1) { // 遍历到最后一个，但是总钱数还是小于value。用例4
                    max = Math.max(max, j - i + 1);
                    break;
                }
            }
        }

        return max;
    }

    /**
     * 适合任取背包
     * @param arr
     * @param c
     * @return
     */
    public static int dpMaxValue(int[] arr, int c) {
        int n = arr.length;
        int[][] dp = new int[n + 1][c + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int j = 1; j <= c; j++) {
            if (arr[0] <= j) {
                dp[0][j] = 1;
            }
        }

        for (int i = 1; i < n; i++) { // 物品
            for (int j = 0; j <= c; j++) { // 背包
                if (j < arr[i - 1]) { // 放弃当前物品
                    dp[i][j] = dp[i - 1][j]; //容量放不下当前这个物品的重量
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - arr[i - 1]] + 1);
                }
            }

        }
        return dp[n - 1][c];
    }


}
